//
// Created by ASUS on 2024/3/20.
//
#include <bits/stdc++.h>
using namespace std;


int _multi_dp_mono_queue(vector<int>& weight, vector<int>& value, vector<int>&cnt ,int target){
	int n=weight.size();
	deque<int> q;
	vector<int> f(target+1,0);
	for(int i=0;i<n;i++){
		auto g=f;
		for(int r=0;r<weight[i];r++){
			for(int j=r;j<=target;j+=weight[i]){
				while(!q.empty()&&j-q.front()>cnt[i]*weight[i]) q.pop_front();
				while(!q.empty()&&g[q.back()]-(q.back()-r)/weight[i]*value[i]<=g[j]-(j-r)/weight[i]*value[i]) q.pop_back();
				q.push_back(j);
				f[j]=g[q.front()]+(j-q.front())/weight[i]*value[i];
			}
		}
	}
	return f[target];
}